package 数据结构.链表;

import java.util.ArrayList;
import java.util.Stack;

/**
 * @author Zhu
 * @Description
 * @create 2023-02-20
 */
public class JZ22链表中倒数最后k个结点 {

    //快慢指针
    public ListNode FindKthToTail(ListNode pHead, int k) {

        ListNode fast = pHead;
        ListNode slow = pHead;
        for (int i = 0; i < k; i++) {
            if (fast == null) {
                return null;
            }
            fast = fast.next;
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    //栈
    public ListNode FindKthToTail2(ListNode pHead, int k) {
        if (pHead == null || k == 0)
            return null;
        Stack<ListNode> s = new Stack<>();
        while (pHead != null) {
            s.push(pHead);
            pHead = pHead.next;
        }
        if(s.size()<k)
            return null;
        ListNode firstNode = s.pop();
        while (--k > 0) {
            ListNode tmp = s.pop();
            tmp.next = firstNode;
            firstNode = tmp;
        }
        return firstNode;
    }

    //ArrayList
    public static ListNode FindKthToTail3 (ListNode pHead, int k) {
        // write code here
        ArrayList<ListNode> a = new ArrayList<>();
        ListNode p = pHead;
        while(p!=null){
            a.add(p);
            p = p.next;
        }
        if(a.size()<k || k==0)
            return null;

        return  a.get(a.size() - k);

    }

    public static void main(String[] args) {
        ListNode head = new  ListNode(1);
        ListNode p = head;

        for(int i=2;i<=5;i++){
            p.next = new ListNode(i);
            p = p.next;
        }

        ListNode node = FindKthToTail3(head, 2);
        System.out.println(node);
    }
}
